#include <stdio.h>
#include <stdlib.h>

// 比较两个整数的大小
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 计算最长非递减子序列的长度并打印序列
void longestNonDecreasingSubsequence(int arr[], int n) {
    if (n == 0) return;

    // dp[i] 存储以 arr[i] 结尾的最长非递减子序列的长度
    int *dp = (int*)malloc(n * sizeof(int));
    // prev[i] 存储最长子序列中 arr[i] 的前一个元素的索引
    int *prev = (int*)malloc(n * sizeof(int));

    // 初始化dp和prev数组
    for (int i = 0; i < n; i++) {
        dp[i] = 1;  // 每个元素自身构成长度为1的子序列
        prev[i] = -1;  // 初始没有前驱
    }

    // 动态规划计算最长非递减子序列
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] <= arr[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;
            }
        }
    }

    // 找到最长子序列的最大长度和结束索引
    int maxLen = 0;
    int endIdx = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            endIdx = i;
        }
    }

    // 回溯构造最长非递减子序列
    int *lis = (int*)malloc(maxLen * sizeof(int));
    int idx = maxLen - 1;
    int current = endIdx;

    while (current != -1) {
        lis[idx] = arr[current];
        current = prev[current];
        idx--;
    }

    // 输出结果
    printf("最长非递减子序列: ");
    for (int i = 0; i < maxLen; i++) {
        printf("%d ", lis[i]);
    }
    printf("\n长度: %d\n", maxLen);

    // 释放内存
    free(dp);
    free(prev);
    free(lis);
}

void main() {
    // 示例数组
    int arr[] = {4, 7, 10, 11, 12, 13, 14, 17, 18, 20, 26, 27, 28, 31, 0, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    longestNonDecreasingSubsequence(arr, n);

}